In recent years cloud computing, in particular the provision of external storage has gained more and more importance. Users can make use of these external storages, for example in the so-called clouds, to store their files. In particular if a very large amount of data needs to be maintained and distributed internally in a company, many companies prefer the cheaper solution of outsourcing data into a cloud. To ensure privacy all the files transmitted to the cloud have to be encrypted.
However, if a user likes to search for data or information satisfying certain criteria a usual search on data cannot be applied since searching on encrypted data is impossible for regular encryption schemes. Therefore the so-called searchable encryption schemes SE have been proposed to overcome this problem and allow users to encrypt data and search afterwards on this data for instance for a keyword within the encrypted file without having to decrypt the file.
However one of the drawbacks of conventional searchable encryption schemes is that they are only concerning about data privacy only. Therefore for example search information could be leaked: If the client uses a conventional searchable encryption scheme the corresponding server in the cloud is enabled to read the encrypted data since the files are all encrypted. Such a conventional searchable encryption scheme, a multikey homomorphic bit encryption scheme, is disclosed in the non-patent literature of Adriana López-Alt, Eran Tromer and Vinod Vaikuntanathan, “On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption”, in: proc. STOC 2012, 1219-1234, ACM, 2012, comprising:                The key generation algorithm KeyGen on input a security parameter n outputs a secret key SK, a public key PK, and an evaluation key EVK.        The encryption algorithm Enc on input a public key PK and a message m, outputs a ciphertext c.        The decryption algorithm Dec on input secret keys SK_1, . . . , SK_k and ciphertext c outputs a message m′.        The evaluation algorithm Eval on input a boolean circuit C, and triples (c_1, PK_1, EVK_1), . . . , (c_k, PK_k, EVK_k), outputs a ciphertext c* which encrypts the message when the circuit C is applied on the messages within the ciphertexts c_1, . . . , c_k.        
When a user then searches for a keyword in the encrypted database he can receive all the files containing the respective keywords. However the search pattern is leaked to the server. The server does not learn the keyword itself but the search pattern. In particular the server can extract the information how often the user searched for a specific keyword and when it happened.
Although a knowledge of a search pattern enables a server only in an indirect way to draw conclusions to a certain extent on the content or type of file on the encrypted user data, it is often enough to obtain relevant personal data: For instance if the search queries the keyword “Oncologist” in the encrypted user data, one can easily reveal that the user suffers from cancer disease.